2466. Count Ways To Build Good Strings

마지막 수정일: 2025. 05. 22.

dp 문제였는데 생각보다 어려웠음, 거의 50분 넘게 걸린 듯
아래는 dp 사용 전 풀이, 테스트는 통과했지만 시간 초과 케이스 존재

JAVASCRIPT 
var countGoodStrings = function(low, high, zero, one) {
	const MOD = 1e9 + 7;
	let arr = [0]
	let cnt = 0;
	while(arr.length !== 0){
		let newArr = []
		arr = arr.flatMap((v)=> [(v+zero) % MOD, (v+one) % MOD]).filter(v=> v<=high);
		cnt += arr.filter((v) => (v>= low) && (v<= high)).length;
	}
	return cnt % MOD;
};

개선 후 코드
dp 사용하여 배열 안에 너무 많은 수가 들어갈 때를 대비하여 성능 개선

JAVASCRIPT 
var countGoodStrings = function(low, high, zero, one) {
	const MOD = 1e9 + 7;
	let dp = new Array(high+1).fill(0)
	dp[0] = 1 // 빈 문자열이 있다고 생각하기 때문에
	for(let i=Math.min(zero, one); i<=high; i++){
		dp[i] = ((dp[i-zero]||0) + (dp[i-one]|| 0))% MOD;
	}
	return dp.slice(low, high +1).reduce((acc, cur)=> (acc+cur)% MOD,0)
};